package 链表;

import java.util.List;

/**
 * https://leetcode-cn.com/leetbook/read/linked-list/fe0kj/
 *
 * 给定单链表的头节点head，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。
 *
 * 第一个节点的索引被认为是 奇数 ， 第二个节点的索引为偶数 ，以此类推。
 *
 * 请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。
 *
 * 你必须在O(1)的额外空间复杂度和O(n)的时间复杂度下解决这个问题。
 *
 */
public class 奇偶链表 {
    public class ListNode {
       int val;
       ListNode next;
       ListNode() {}
       ListNode(int val) { this.val = val; }
       ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }


    public ListNode oddEvenList2(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode t1 = head; //指向奇链表
        ListNode t2 = head.next; //指向偶链表
        ListNode t2Head = t2; //指向偶链表头

        while(t2!=null && t2.next!=null){ //保证节点为偶数个的情况
            t1.next = t2.next;
            t1 = t1.next;
            t2.next = t1.next;
            t2 = t2.next;
        }
        t1.next = t2Head; //连接奇偶链表
        return head;
    }

    public ListNode oddEvenList(ListNode head) {
        if(head == null || head.next == null) return head;

        ListNode newHead1 = new ListNode(0); //连接奇链表
        ListNode newHead2 = new ListNode(0); //连接偶链表
        ListNode tmp1 = newHead1;
        ListNode tmp2= newHead2;
        ListNode tmp3 = head;

        ListNode newHead = new ListNode(0); //返回的新链表
        ListNode res = newHead;

        int size = size(head);
        for (int i = 1; i <=size; i++) {
            if((i&1)!=0){ //奇数
                tmp1.next = tmp3;
                tmp1 = tmp1.next;
            }else{
                tmp2.next = tmp3;
                tmp2 = tmp2.next;

            }
            tmp3 = tmp3.next;
        }

        tmp1 = newHead1.next;
        tmp2 = newHead2.next;
        while(tmp1!=null){
            res.next = tmp1;
            tmp1 = tmp1.next;
            res = res.next;
        }
        while(tmp2!=null){
            res.next = tmp2;
            tmp2 = tmp2.next;
            res = res.next;
        }


        return newHead.next;
    }

    private int size(ListNode head){
        if(head == null) return 0;
        int size = 0;
        ListNode tmp = head;
        while(tmp!=null){
            size++;
            tmp = tmp.next;
        }
        return size;
    }



}
